
#ifndef _ALLOCATOR_CACHE_H_
#define _ALLOCATOR_CACHE_H_

namespace share
{

#define ALLOC_MIN	(8192)

#define BOUNDARY_INDEX 12
#define BOUNDARY_SIZE (1 << BOUNDARY_INDEX)

#define  ALLOC_ALIGN( size, boundary )		\
	(((size) + ((boundary) - 1)) & ~((boundary) - 1))

#define ALLOC_ALIGN_DEFAULT( size )	ALLOC_ALIGN( size, 8 )

#define ALLOC_MAX_FREE_UNLIMITED	(0)

#define MEMNODE_SIZE	ALLOC_ALIGN_DEFAULT( sizeof(MemNode) )

template <class LOCK>
class Allocator_Cache: public Allocator_Impl
{
	enum
	{
		MAX_INDEX = 20
	};
	typedef struct _mem_node
	{
		_mem_node		*next_;
		_mem_node		**ref_;
		size_t		index_;
		char		*avail_;
		char		*endp_;
	} MemNode;

public:
	Allocator_Cache( void )
	{
		max_index_ = 0;
		max_free_index_ = 0;
		current_free_index_ = 0;
		memset( free_node_, 0, sizeof( free_node_ ) );
	}
	~Allocator_Cache( void )
	{
		clear( );
	};

	inline void *alloc( size_t size )
	{
		MemNode *node = this->node_alloc( size );

		if( !node )
			return 0;

		return node->avail_;
	}

	inline void free( void *block )
	{
		MemNode *node = ( MemNode* )(( char* ) block - MEMNODE_SIZE );
		node_free( node );
	}

	void clear( )
	{
		MemNode *node, *next;
		int index = 0;
		Guard<LOCK> guard( lock_ );

		while(( node = free_node_[ index ] ) != 0 && index < MAX_INDEX )
		{
			while( node )
			{
				next = node->next_;
				::free( node );
				node = next;
			}

			index ++;
		}

		max_index_ = 0;
		max_free_index_ = 0;
		current_free_index_ = 0;
		memset( free_node_, 0, sizeof( free_node_ ) );
	}

private:

	inline MemNode *node_alloc( size_t size )
	{
		MemNode *node;
		MemNode **ref;
		size_t index;
		size_t max_index;

		size = ALLOC_ALIGN( size, BOUNDARY_SIZE );

		//size = ALLOC_ALIGN( 100, 16 );
		if( size <= 0 )
			return 0;

		if( size < ALLOC_MIN )
			size = ALLOC_MIN;

		index = ( size >> BOUNDARY_INDEX ) - 1;

		if( index >= 0xffffffff )
			return 0;

		Guard<LOCK> guard( lock_ );

		if( index <= this->max_index_ )
		{
			max_index = max_index_;
			ref = &free_node_[ index ];
			size_t i = index;

			while( *ref == 0 && i < max_index )
			{
				ref ++;
				i ++ ;
			}

			if(( node = *ref ) != 0 )
			{
				if(( *ref = node->next_ ) == 0 && i >= max_index )
				{
					do
					{
						ref --;
						max_index --;
					}
					while( *ref == 0 && max_index > 0 );
				}

				max_index_ = max_index;
			}

			current_free_index_ += node->index_;

			if( current_free_index_ > max_free_index_ )
				current_free_index_ = max_free_index_;

			node->next_ = 0;
			node->avail_ = ( char* ) node + MEMNODE_SIZE;
			return node;
		}
		else if( free_node_[ 0 ] )
		{
			ref = &free_node_[ 0 ];

			while(( node = *ref ) == 0 && index > node->index_ )
				ref = &node->next_;

			if( node )
			{
				*ref = node->next_;
				current_free_index_ += node->index_;

				if( current_free_index_ > max_free_index_ )
					current_free_index_ = max_free_index_;

				node->next_ = 0;
				node->avail_ = ( char* ) node + MEMNODE_SIZE;
				return node;
			}
		}

		if(( node = ( MemNode* ) malloc( size ) ) == 0 )
			return 0;

		node->next_ = 0;
		node->index_ = index;
		node->avail_ = ( char* ) node + MEMNODE_SIZE;
		node->endp_ = ( char* ) node + size;
		return node;
	}

	inline void node_free( MemNode *node )
	{
		size_t	index;
		size_t	max_index;
		MemNode	*next;
		MemNode	*freelist = 0;
		size_t	max_free_index;
		size_t	current_free_index;

		max_index = max_index_;
		max_free_index = max_free_index_;
		current_free_index = current_free_index_;

		Guard<LOCK> guard( lock_ );

		do
		{
			next = node->next_;
			index = node->index_;

			if( max_free_index != ALLOC_MAX_FREE_UNLIMITED &&
			        index > current_free_index )
			{
				node->next_ = freelist;
				freelist = node;
			}
			else if( index < MAX_INDEX )
			{
				if(( node->next_ = free_node_[ index ] ) == 0 &&
				        index > max_index )
				{
					max_index = index;
				}

				free_node_[ index ] = node;

				if( current_free_index >= index )
					current_free_index -= index;
				else
					current_free_index = 0;
			}
			else
			{
				node->next_ = free_node_[ 0 ];
				free_node_[ 0 ] = node;

				if( current_free_index >= index )
					current_free_index -= index;
				else
					current_free_index = 0;
			}
		}
		while(( node = next ) != 0 );

		max_index_ = max_index;
		current_free_index_ = current_free_index;

		while( freelist )
		{
			node = freelist;
			freelist = node->next_;
			::free( node );
		}
	}
private:
	size_t	max_index_;
	size_t	max_free_index_;
	size_t	current_free_index_;
	MemNode	*free_node_[ MAX_INDEX ];
	LOCK	lock_;
};

}
#endif
